package tree;

public class QuadTreeExample {
    public static void main(String[] args) {
        QuadTreeNode<String> root = new QuadTreeNode<String>("Hello", 10, 10);
        System.out.println("Here's the root: " + root);
        QuadTree<String> quadTree = new QuadTree<String>(root);
        quadTree.insert(new QuadTreeNode<String>("World", 5, 7));
        quadTree.insert(new QuadTreeNode<String>(" YahoooO!!", 25, -7));
        System.out.println("After insertion:" + quadTree);
    }

    static class QuadTreeNode<T> {
        T data;
        private QuadTreeNode leftTop;
        private QuadTreeNode leftBottom;
        private QuadTreeNode rightTop;
        private QuadTreeNode rightBottom;
        private int x, y;

        QuadTreeNode(T data, int x, int y) {
            this.data = data;
            this.y = y;
            this.x = x;
        }

        QuadTreeNode(QuadTreeNode leftTop, QuadTreeNode leftBottom, QuadTreeNode rightTop, QuadTreeNode rightBottom, int x, int y, T data) {
            this.leftTop = leftTop;
            this.leftBottom = leftBottom;
            this.rightTop = rightTop;
            this.rightBottom = rightBottom;
            this.x = x;
            this.y = y;
            this.data = data;
        }

        @Override
        public String toString() {
            return "QuadTreeNode{" +
                    "<" + x + ", " + y + "> [" + data + "]" +
                    (leftTop == null ? "" : ", leftTop=" + leftTop.toString()) +
                    (leftBottom == null ? "" : ", leftBottom=" + leftBottom.toString()) +
                    (rightTop == null ? "" : ", rightTop=" + rightTop.toString()) +
                    (rightBottom == null ? "" : ", rightBottom=" + rightBottom.toString()) +
                    '}';
        }
    }

    static class QuadTree<T> {
        QuadTreeNode<T> root;

        QuadTree(QuadTreeNode<T> root) {
            this.root = root;
        }

        @Override
        public String toString() {
            return "QuadTree{" +
                    "root=" + root +
                    '}';
        }

        public void insert(QuadTreeNode<T> node) {
            if (root == null) root = new QuadTreeNode<T>(node.data, node.x, node.y);
            else {
                int rootX = root.x;
                int rootY = root.y;

                boolean isLeft = (rootX > node.x);
                boolean isDown = (rootY > node.y);
                if (rootX == node.x && rootY == node.y) {
                    root.data = node.data;
                    return;
                }
                QuadTreeNode<T> newNode = new QuadTreeNode<T>(node.data, node.x, node.y);
                if (isLeft) {
                    if (isDown) root.leftBottom = newNode;
                    else root.leftTop = newNode;
                } else {
                    if (isDown) root.rightBottom = newNode;
                    else root.rightTop = newNode;
                }

            }
        }
    }
}
